package com.cqs.leetcode.backtrack;

import java.util.*;

/**
 * @author lixiaowen
 * @create 2020-01-07
 */
public class SubSetsII90 {

    /**
     * 1. DP + Set去重
     */
    static class Solution {
        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            result.add(new MyList());
            if (nums == null || nums.length == 0) return result;
            LinkedHashSet<List<Integer>> set = new LinkedHashSet<>();
            set.add(new MyList());
            subsetsWithDup(nums, set, 0);
            result.clear();
            result.addAll(set);
            return result;
        }

        public void subsetsWithDup(int[] nums, final LinkedHashSet<List<Integer>> set, int level) {
            if (level >= nums.length) return;
            int len = set.size();
            Iterator<List<Integer>> iterator = set.iterator();
            LinkedHashSet<List<Integer>> tmp = new LinkedHashSet<>();
            while (--len >= 0) {
                List<Integer> list = iterator.next();
                MyList nlist = new MyList(list);
                nlist.add(nums[level]);
                tmp.add(nlist);
            }
            set.addAll(tmp);
            tmp.clear();
            subsetsWithDup(nums, set, level + 1);
        }

        class MyList extends LinkedList<Integer> {


            public MyList(Collection<? extends Integer> c) {
                super(c);
            }

            public MyList() {
            }

            @Override
            public boolean add(Integer integer) {
                //有序插入
                for (int i = 0; i < this.size(); i++) {
                    if (this.get(i) >= integer) {
                        this.add(i, integer);
                        return true;
                    }
                }
                this.add(this.size(), integer);
                return true;
            }
        }

    }

    /**
     * 转化为组合
     * 回溯法
     */
    static class Solution2 {

        public List<List<Integer>> subsetsWithDup(int[] nums) {
            List<List<Integer>> result = new ArrayList<>();
            result.add(new ArrayList<>());
            if (nums == null) return result;
            Arrays.sort(nums);
            for (int i = 1; i <= nums.length; i++) {
                result.addAll(subsetsWithDup0(nums, i));
            }
            return result;
        }

        private List<List<Integer>> subsetsWithDup0(int[] nums, int k) {
            List<List<Integer>> result = new ArrayList<>();
            combination(nums, k,1, -1, result, new ArrayList<>());
            return result;
        }


        /**
         * @param nums
         * @param k
         * @param level
         * @param maxUsedIdx
         * @param result
         * @param list
         */
        private void combination(int[] nums, int k, int level, int maxUsedIdx,
                                 List<List<Integer>> result, List<Integer> list) {
            if (level > k) {
                result.add(new ArrayList<>(list));
                return;
            }
            Set<Integer> levelUsed = new HashSet<>();
            for (int i = maxUsedIdx + 1; i < nums.length - (k - level); i++) {
                //去重 -- 分支剪切
                if (levelUsed.contains(nums[i])) continue;
                list.add(nums[i]);
                combination(nums, k, level + 1, i, result, list);
                //记录本层使用过的元素
                levelUsed.add(nums[i]);
                list.remove(list.size() - 1);
            }
        }

    }


    public static void main(String[] args) {
//        Solution solution = new Solution();
        Solution2 solution = new Solution2();
        List<int[]> test = new ArrayList<>();
        test.add(new int[]{4, 4, 4, 1, 4});
        test.add(new int[]{1, 2, 2});
        test.forEach(nums -> {
            System.out.println(solution.subsetsWithDup(nums));
        });
    }
}
